The Talk in a Nutshell

Practical Motivation

The City of Berlin

Q: How to draw the map of the city from a noisy point-cloud of GPS locations?

A Reconstruction of Berlin

Source: mapconstruction.org

Reconstruction Goals

  • Shape: A Shape is modeled as a metric space

  • Sample: A finite 𝒮⊂ℝN\mathcal S\subset\mathbb R^N with small Hausdorff distance dH(𝒢,𝒮)d_{\mathrm H}(\mathcal G, \mathcal S)

  • Goal: Infer the topology of 𝒢\mathcal G from 𝒮\mathcal S.

    • Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of 𝒢\mathcal G

    • construct a topological space 𝒢̂\hat{\mathcal G} from 𝒮\mathcal S so that

      • 𝒢̂\hat{\mathcal G} is homotopy equivalent to 𝒢\mathcal G (topological reconstruction)
      • 𝒢̂⊂ℝN\hat{\mathcal G}\subset\mathbb R^N and dH(𝒢̂,𝒮)d_{\mathrm H}(\hat{\mathcal G}, \mathcal S) small (geometric reconstruction)

The Vietoris–Rips Complex

  • a metric space (X,dX)(X,d_X)

  • a scale β>0\beta>0

  • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex

    • XX is the vertex set
    • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter less than β\beta is a kk-simplex.

A single Vietoris–Rips complex fails to be topologically faithful, no matter the sample density

Remedy 1: ε\varepsilon-path Metric

  1. Fix a positive ε\varepsilon: proportional to dH(𝒮,𝒢)d_H(\mathcal S, \mathcal G);

  2. Compute ε\varepsilon-neighborhood graph on 𝒮\mathcal S: ℛε(1)(𝒮)\mathcal R^{(1)}_\varepsilon(\mathcal S);

  3. Define d𝒮ε(a,b)d_{\mathcal S}^\varepsilon(a,b) to be the shortest path metric on ℛε(1)(𝒮)\mathcal R^{(1)}_\varepsilon(\mathcal S);

  4. Denote by ℛβε(S)\mathcal{R}_\beta^\varepsilon(S) the Vietoris–Rips complex of 𝒮\mathcal S under d𝒮εd^\varepsilon_{\mathcal S}.

ε\varepsilon-path Metric on 𝒮\mathcal S

Quasi-isometry (Komendarczyk, Majhi, and Tran 2024)

For a dense enough sample 𝒮\mathcal S of 𝒢\mathcal G, d𝒮εd^\varepsilon_{\mathcal S} is quasi-isometric to the length metric on 𝒢\mathcal G.

Remedy 2: Large-scale Distortion

  • A finite sample around a corner does not see the corner
  • Global distortion: δ(𝒢)=supa≠bd𝒢L(a,b)∥a−b∥\delta(\mathcal G)=\sup_{a\neq b}\frac{d^L_{\mathcal G}(a,b)}{\|a-b\|}
  • Large-scale distortion: δRε(𝒢)=supdL(a,b)≥Rd𝒢L(a,b)d𝒢εL(a,b)\delta^\varepsilon_R(\mathcal G)=\sup_{d^L(a,b)\geq R}\frac{d^L_{\mathcal G}(a,b)}{d^L_{\mathcal G^\varepsilon}(a,b)}

Limit (Komendarczyk, Majhi, and Tran 2024)

For any R>0R>0, δRε(𝒢)→1\delta^\varepsilon_R(\mathcal G)\to1 as ε→0\varepsilon\to0, provided 𝒢\mathcal G is compact.

Topological Reconstruction

Metric Graph Reconstruction (Komendarczyk, Majhi, and Mitra 2025)

Let 𝒢⊂ℝN\mathcal G \subset \mathbb{R}^N be a compact, connected metric graph.
Fix any ξ∈(0,14)\xi\in\left(0,\frac{1}{4}\right). For any positive β<ℓ(𝒢)4\beta<\frac{\ell(\mathcal G)}{4}, choose a positive ε≤β3\varepsilon\leq\frac{\beta}{3} such that δβε(𝒢)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(\mathcal G)\leq\frac{1+2\xi}{1+\xi}.

If 𝒮⊂ℝN\mathcal S\subset \mathbb R^N is such that dH(𝒢,𝒮)<12ξεd_H(\mathcal G,\mathcal S)<\tfrac{1}{2}\xi\varepsilon, then we have a homotopy equivalence ℛβε(𝒮)≃𝒢\mathcal R^\varepsilon_\beta(\mathcal S)\simeq \mathcal G.

Fixing ξ=1/6\xi=1/6, we get a simpler but weaker statement.

Let 𝒢⊂ℝN\mathcal G \subset \mathbb{R}^N be a compact, connected metric graph.
For any positive β<ℓ(𝒢)/4\beta<\ell(\mathcal G)/4, choose a positive ε≤β/3\varepsilon\leq\beta/3 such that δβε(𝒢)≤8/7\delta^{\varepsilon}_{\beta}(\mathcal G)\leq8/7. If 𝒮⊂ℝN\mathcal S\subset \mathbb R^N and dH(𝒢,𝒮)<ε/12d_H(\mathcal G,\mathcal S)<\varepsilon/12, then we have a homotopy equivalence ℛβε(𝒮)≃𝒢\mathcal R^\varepsilon_\beta(\mathcal S)\simeq\mathcal G.

Vietoris–Rips Shadow

  • Geometric reconstruction: entails constructing 𝒢̂⊂ℝN\hat{\mathcal G}\subset\mathbb R^N from samples so that
    • 𝒢̂≃𝒢\hat{\mathcal G}\simeq \mathcal G & dH(𝒢̂,𝒮)d_H(\hat{\mathcal G}, \mathcal S) is small
  • Vietoris–Rips complexes are abstract, hence contain only topological information
  • A good candidate for 𝒢̂\hat{\mathcal G} is the shadow of a topologically-faithful Vietoris–Rips.

𝒦\mathcal K

  • Shadow: For simplicial complex 𝒦\mathcal K with vertices from ℝN\mathbb R^N is the union of the (Euclidean) convex hulls of simpices σ∈𝒦\sigma\in\mathcal K

  • Notorious for being topologically unfaithful

    • Chambers et al. (2010); Adamaszek, Frick, and Vakili (2017)

sh(𝒦)\mathrm{sh}(\mathcal K)

Graph Reconstruction via Shadow

Geometric Reconstruction (Komendarczyk, Majhi, and Mitra 2025)

Let 𝒢⊂ℝ2\mathcal G \subset \mathbb{R}^2 a graph. Fix any ξ∈(0,1−Θ6)\xi\in\left(0,\frac{1-\Theta}{6}\right). For any positive β<min{Δ(𝒢),ℓ(𝒢)12}\beta<\min\left\{\Delta(\mathcal G),\frac{\ell(\mathcal G)}{12}\right\}, choose a positive ε≤(1−Θ)(1−Θ−6ξ)12β\varepsilon\leq\frac{(1-\Theta)(1-\Theta-6\xi)}{12}\beta such that δβε(𝒢)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(\mathcal G)\leq\frac{1+2\xi}{1+\xi}.

If 𝒮⊂ℝ2\mathcal S\subset \mathbb R^2 and dH(𝒢,𝒮)<12ξεd_H(\mathcal G, \mathcal S)<\tfrac{1}{2}\xi\varepsilon, then the shadow sh(ℛβε(𝒮))sh(\mathcal R_\beta^\varepsilon(\mathcal S)) is homotopy equivalent to 𝒢\mathcal G. Moreover, dH(sh(ℛβε(𝒮)),𝒢)<(β+12ξε)d_H(sh(\mathcal R_\beta^\varepsilon(\mathcal S)),\mathcal G)<\left(\beta+\frac{1}{2}\xi\varepsilon\right).

  • Θ∈(0,1)\Theta\in(0,1): depends on the angles between tangents of edges at the graph vertices
  • Δ(G)\Delta(G): Shadow radius positive number for graphs with smooth edges
  • 𝒢\mathcal G is planar

Future Directions

  • The general case: 𝒢⊂ℝN\mathcal G\subset\mathbb R^N

    • in preparation with Kazuhiro Kawamura & Atish Mitra

  • Use discrete Morse theory to perform organized collapses of higher dimensional simplices of shadow for homeomorphic reconstruction

  • Submanifold reconstruction via Vietoris–Rips shadow

    • Topological reconstruction already done in (Majhi 2024)